const insertSearch = (arr, value) => {
  let start = 0
  let end = arr.length - 1
  while (start <= end) {
    // 对二分查找的点做了改进
    let mid = start + (value - arr[start]) / (arr[end] - arr[start]) * (end - start)
    mid = mid.toFixed(0)
    if (arr[mid] == value) {
      return mid
    } else if (arr[mid] > value) {
      end = mid - 1
    } else {
      start = mid + 1
    }
  }
  return -1
}
// 非递归
const testArr = [2, 1, 10, 8, 5, 4, 3, 9, 6, 0, -1, -2, 2 * 1, 3 * -1, 1 - 5, 7]
testArr.sort((a, b) => {
  return a - b
})
console.log(testArr);
console.log(insertSearch(testArr, -2));

// * 插值查找是对二分查找的进一步改进
// * 不支持浮点数
// 不仅是一个排序好的序列，而且序列的步长大致相同，使用插值查找会更快的找到目标。